package leetcode.editor.week.week307;

// 2384. 最大回文数字
// https://leetcode.cn/problems/largest-palindromic-number/
public class Solution2384 {
    public String largestPalindromic(String num) {
        int[] cnt = new int[10];
        // 记录个数
        for (int i = 0; i < num.length(); i++) {
            cnt[num.charAt(i) - '0']++;
        }

        // ans1 表示对应的部分中的前一半，ans2 是 ans 的倒序
        StringBuilder ans1 = new StringBuilder();
        String ans2 = "";
        // 求回文串两边对应的部分，偶数个数的都添加进来
        for (int i = 9; i >= 0; i--) {
            // 已经枚举到了 0，但是之前从来没有加入过别的数字。此时加入 0 将会导致前导 0，因此直接结束
            if (i == 0 && ans1.length() == 0) break;
            // 在这部分中出现过的数必须出现偶数次，取一半
            int t = cnt[i] / 2;
            // 进行拼接
            for (int j = 0; j < t; j++) ans1.append(i);
            // hash表减去使用过的个数
            cnt[i] -= 2 * t;
            ans2 = ans1.toString();
        }

        // 进行反转拼接在后边
        ans2 = reverse(ans2);

        // 看看是否还有剩下的数，可以作为中间单独的一个数字
        for (int i = 9; i >= 0; i--) {
            if (cnt[i] > 0) {
                // 此时 0 无需跳过，因为单独一个 0 是合法的答案
                // 也就是加在ans1的最后，整个字符串中间
                ans1.append(i);
                break;
            }
        }

        // 追加逆序的ans2
        return ans1.append(ans2).toString();
    }

    private String reverse(String ans2) {
        int i = 0, j = ans2.length() - 1;
        char[] arr = ans2.toCharArray();
        while (i < j) {
            char t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            i++;
            j--;
        }

        return new String(arr);
    }
}
